from typing import List
"""
349. 两个数组的交集
简单
相关标签
相关企业
给定两个数组 nums1 和 nums2 ，返回 它们的 
交集
 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

 

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的
 

提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000
"""

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
#        方法2：增序排序后+利用双指针
        nums1.sort()
        nums2.sort()
        index1 = index2 =0
        newlist = list()
        while index1< len(nums1) and index2< len(nums2):
            if nums1[index1]<nums2[index2]:
                index1+=1
            elif nums2[index2]<nums1[index1]:
                index2+=1
            #    若newlist不为空且新加入的数字不等于上一次加入的数字
            else:
                if not newlist or nums1[index1]!=newlist[-1]:
                    newlist.append(nums1[index1])
                    index1+=1
                    index2+=1
        return newlist


if __name__ == '__main__':
    print(Solution().intersection([1, 3, 4], [2, 4, 8]))
